package 剑指offer;

/**
 * @author zhangjunfei
 * @date 2023/8/25 10:32
 */
public class O_13 {
    public int movingCount(int m, int n, int k) {
        boolean[][] visit = new boolean[m][n];
        return dfs(0, 0, m, n, k,visit);
    }

    int dfs(int i, int j,int m,int n, int k,boolean[][] visit) {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || visit[i][j]) {
            return 0;
        }
        if (((i/10)+(i%10)+(j/10)+(j%10))>k){
            return 0;
        }
        visit[i][j] = true;
        int i1 = dfs(i + 1, j, m, n, k,visit)
                + dfs(i - 1, j, m, n, k,visit)
                + dfs(i, j + 1, m, n, k,visit)
                + dfs(i, j - 1, m, n, k,visit);

        return i1+1;

    }
}
